/*

Google

给定一个长度为N的整数数组（元素有正有负），
求所有元素之和，
最大的一个子数组。
分析算法时空复杂度。
不必写代码。 
*/
#include "junix.h"

void max_sub2(int v[], int size, int& max,int& tail) {
	if (size==1) {
		max = v[0];
		if (v[0]>=0) 
			tail = v[0];
		else 
			tail = 0;

		return;
	}

	int m,t;
	max_sub2(v,size-1,m,t);
	if (v[size-1]>=0) 
		tail = t+v[size-1];
	 else 
		tail = 0;
	
	if (tail > m) 
		max = tail;
	else 
		max = m;
}

int max_sub(int v[], int size) {
	int tail=0, max =0;
	max_sub2(v,size,max,tail);
	return max;
}

int main(){
	int v[]={1,2,3,4,-5,6,7,8,-9,10,3,5};
	std::cout<<max_sub(v,sizeof(v)/sizeof(v[0]))<<std::endl;
}
